The present invention relates to design automation for embedded system design and particularly to structural analysis of software programming language and hardware description language specifications.
An embedded system is a computer with a specific software application that interacts with its environment. The state of technology for embedded system design emphasizes concurrent design of the hardware and software, commonly referred to as “codesign”. Software portions of an embedded system are often specified using a programming language that is subsequently compiled into machine code suitable for execution by a reprogrammable processing element. Behavioral aspects of hardware portions of an embedded system are often specified using a hardware description language that is subsequently compiled into hardware circuits. A useful codesign methodology includes design automation tools that assist a designer in the manipulation, analysis, and transformation of hardware and software source code specifications.
The programming interface between software and hardware processing elements can be viewed as a collection of shared memory locations and procedures that are sensitive to or activated by access to memory locations. The shared memory may reside on a variety of physical components, for example microprocessor registers, main storage memory, or a coprocessor such as an I/O controller. The software procedures use load and store operations to access shared memory, including registers on a coprocessor. The hardware behavioral description has equivalent operations to access shared memory. The programming interface across the hardware-software boundary is commonly specified in databooks, programming guides, and other static descriptions. Such written descriptions make it difficult for a designer to understand the interacting behavior of the hardware-software interface. A further drawback of written descriptions is the difficulty of correlating described behavior with observed behavior during debugging activity. A beneficial way to describe software and hardware behavior is in terms of source code specifications, and design automation tools that aid in the understanding of such source code specifications are beneficial for a codesign methodology.
Program slicing is a software analysis method to find the subset of program statements that may affect the computation at a particular program point. This program point, which may be defined as a statement or a particular variable used at a statement, is called the slicing criterion. In the simple case of a single entry, single-exit program, a slice is determined by finding all the transitive data flow and control dependences that lead to the slicing criterion. Slicing is useful as a maintenance or reuse tool for activities such as program understanding, debugging, regression testing, and function extraction from existing code. As an interactive tool, a program slicer facilitates understanding of relevant portions of the software by directly transforming the source code into a simplified specification.
Program slicing was introduced by Weiser [“Program Slicing,” IEEE Transactions on Software Engineering, vol. 10, no. 4, pp. 352-357, 1984] who defined a slicing criterion as any subset of program variables at a statement. The program slice consists of those statements that may affect the values of the criterion variables, including whether or not the statement executes. The Weiser slice is computed by iteratively solving data and control flow equations based on a control flow graph representation of a software program.
A control flow graph (CFG) is a representation of a program suitable for systematic analysis, derived from an imperative language source code specification using standard techniques as described, for example, by Aho et al. in [Compilers, Principles, Techniques, and Tools, Addison-Wesley, 1986]. A control flow graph consists of operations and control paths between operations. A flow graph is an equivalent representation that consists of basic blocks and control paths between the basic blocks. A basic block is a sequence of operations that always execute as a group. A control flow graph is a common representation for source code analysis, and standard techniques exist to find control dependence relationships and data flow dependence relationships.
Program slice computation was also formulated as a graph reachability problem as described in U.S. Pat. No. 5,161,216 to Reps et al. (1992). The graph-based approach is better suited for programs with multiple procedures, as it can explicitly represent procedure calling contexts. The methods described by Reps et al. are based on specialized control and data dependences to analyze interprocedural relationships of sequential software programs.
In a graph-based approach, a system dependence graph (SDG) summarizes the control and data dependences of an entire program. The SDG is composed of one or more procedure dependence graphs (PDG), where each PDG summarizes intra-procedure control and data flow dependences. The PDGs, one for each procedure in the program, are connected in the SDG with edges that summarize the inter-procedure data and control dependences. A graph-based approach allows a more precise calculation of a slice compared to the use of data and control equations, as explained by Agrawal et al. [“Dynamic program slicing,” ACM Sigplan Not. vol. 25, no. 6, pp. 246-256, 1990] and Reps et al. [“Precise interprocedural chopping,” Proc. 3rd ACM SIGSOFTSymposium onthe Foundations of Software Engineering, pp. 41-52, 1995]. A more precise slice is superior in the sense that it includes fewer statements in a slice.
Extensions to apply graph-based program slicing for concurrent programs were proposed by Krinke [“Static slicing of threaded programs,” ACMSigplan Not. vol. 33, no. 7, pp. 35-42, 1998] and Nanba et al. [“Slicing Concurrent Programs,” Proc. Int. Symp. Software Testingand Analysis pp. 180-190, 2000], though with severe restrictions on the type of software programs that could be analyzed. A threaded CFG was defined such that all parallel threads were explicitly indicated in a single CFG, which then could be analyzed to find interference dependences, which are data flow dependences between parallel software threads, as well as feasible execution order for the multiple software threads.
Hardware description languages such as VHDL or Verilog specify the structure and behavior of electronic circuits. The basics of applying slicing to VHDL descriptions were introduced by Iwaihara et al. [“Program slicing on VHDL descriptions and its applications,” Third Asian Pacific Conf Hardware Description Languages, pp. 132-139, 1996.] using techniques based on a data and control flow equations. Iwaihara et al. defined a signal dependence to represent both a control dependence that activates an operation and a data dependence between potentially concurrent operations. The data dependence aspect is similar to the interference dependence proposed by Krinke et al., supra.
An application of slicing for Verilog hardware descriptions based on data and control flow equations for the purpose of verification testing was proposed by [“Program slicing for hierarchical test generation,” Proc 20th VLSI Test Symposium, pp. 237-243, 2002.]. Vedula et al. described a signal dependence as a pure control dependence and developed theoretical ideas to support the application of program slicing for automated test pattern generation.
A work by Clarke et. al. [“Program slicing of hardware description languages,” Proc. 10th Adv. Res. Work. Conf Correct Hard.Design and Ver. Methods, pp. 298-312, 1999.] defined slicing for VHDL based on a graph representation derived by first mapping VHDL language constructs to a procedural software language such as C. Clarke et al. mapped a signal dependence to a function call and introduced a synthetic master process that continuously invokes the non-halting VHDL procedures. The work by Clark et al. does not address the issue of analyzing software and hardware concurrently.